/*
两种快排的方式
1. 横扫区间，枢轴不动，最后指定枢轴
2. 横扫区间，枢轴随动，最后指定枢轴
快排不稳定，复杂度情况【nlogn,n^2】
*/
#include<iostream>
using namespace std;
void Print(int* arr,int len){
    for(int i = 0;i < len;i++){
        cout<<*(arr+i)<<"  ";
    }
    cout<<endl;
}
void Swap(int& a,int& b){
    int tmp = a;
    a = b;
    b = tmp;
}
void QuickSortWiki(int* arr,int begin,int end){
    if(begin >= end){
        return ;
    }
    else{
        int pivot_index = begin;
        int pivot_value = arr[pivot_index];
        for(int i = begin+1;i <= end;i++){  //没动过第一个元素，因为它是基值
            if(arr[i] < pivot_value){
                pivot_index++;      //这个实际上是要先把枢轴的位置定下来，有多少个小于基值，枢轴就要向右移动多少。
                Swap(arr[i],arr[pivot_index]);//在移动过程中pivot_index <= i,因此每当有小于基值的时候就表示当前的枢轴后还有比基值更小的值，将该值与枢轴上的值交换即可保证小于基值的值都在枢轴左边（开头的基值除外）。
            }
        }
        Swap(arr[begin],arr[pivot_index]);  //此时数组第一位基值，枢轴（包含）以左都小于基值，基值与枢轴的值调换即可。此时枢轴一边都小于基值，右边都大于等于基值。
        QuickSortWiki(arr,begin,pivot_index-1);
        QuickSortWiki(arr,pivot_value+1,end);
    }
}
void QuickSort(int* arr,int begin,int end){
    if(begin >= end){
        return ;
    }
    else{
        int left = begin,right = end;
        int pivot_value = arr[begin];
        while(left < right){
            if(arr[left+1] < pivot_value){	//枢轴是不动的，直接从数组的开头开始填比基值小的
                arr[left] = arr[left+1];
                left++;	//每次填完都往后挪
            }
            else{
                Swap(arr[left+1],arr[right]); //从数组末尾填比基值大的
                right--;
            }
        }
        arr[left] = pivot_value;    //此时i，j将相遇，设置基值。
        QuickSort(arr,begin,left-1);
        QuickSort(arr,left+1,end);
    }
}
int main(){
    int arr[10] = {5,7,3,2,1,4,6,9,8,0};
    Print(arr,10);
    QuickSortWiki(arr,0,9);
    Print(arr,10);
    return 0;
}